package leetcode.code1851;

import java.util.PriorityQueue;
import java.util.TreeMap;


//Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
/**
 *
 * 堆 和 有序表 <br>
 * 执行用时：715 ms, 在所有 Java 提交中击败了6.12%的用户
 *
 * 内存消耗：108.9 MB, 在所有 Java 提交中击败了6.12%的用户
 *
 * 通过测试用例：42 / 42
 */
public class Solution2 extends Solution1851 {

	int LEFT = 0;
	int RIGHT = 1;

	@Override
	public int[] minInterval(int[][] intervals, int[] queries) {
		PriorityQueue<int[]> p = new PriorityQueue<>((a, b) -> {
			if (a[1] != b[1]) {// 左端优先
				return a[1] - b[1];
			} else if (a[2] != b[2]) {
				return a[2] - b[2];// 右端优先
			} else {
				return a[3] - b[3];// 小区间优先
			}
		});
		for (int[] interval : intervals) {
			int L = interval[0];
			int R = interval[1];
			int size = R - L + 1;
			p.add(new int[] { LEFT, L, R, size });
			p.add(new int[] { RIGHT, R, R, size });
		}
		// 右界靠左优先，相同右界小size优先 错了
		PriorityQueue<int[]> rightRge = new PriorityQueue<>((a, b) -> a[2] - b[2]);
		// 左边界，左边界，size，右边界 错了
		PriorityQueue<int[]> leftRge = new PriorityQueue<>((a, b) -> a[2] - b[2]);
		rightRge.add(new int[] { -1, Integer.MAX_VALUE, Integer.MAX_VALUE });
		leftRge.add(new int[] { -1, Integer.MAX_VALUE, Integer.MAX_VALUE });
		TreeMap<Integer, Integer> tm = new TreeMap<>();// <序号，最小区间>
		int[] curRight = null;
		int[] curLeft = null;
		while (!p.isEmpty()) {
			int[] cur = p.poll();
			int LR = cur[0], L = cur[1], R = cur[2], size = cur[3];
			if (LR == LEFT) {
				rightRge.add(new int[] { L, R, size });
				leftRge.add(new int[] { L, R, size });
			}
			while (rightRge.peek()[1] < L || (LR == RIGHT && rightRge.peek()[1] == L)) {
				rightRge.poll();
			}
			while (leftRge.peek()[1] <= L) {// || (LR == LEFT && leftRge.peek()[1] == L)
				leftRge.poll();
			}
			curRight = rightRge.peek();
			curLeft = leftRge.peek();
			int curSizeRight = curRight[2];
			int curSizeLeft = curLeft[2];
			int min = Math.min(size, curSizeRight);
			min = Math.min(min, curSizeLeft);
			if (tm.containsKey(L)) {
				min = Math.min(min, tm.get(L));
			}
			tm.put(L, min);
			if (LR == RIGHT && size != Integer.MAX_VALUE) {
				p.add(new int[] { RIGHT, L + 1, Integer.MAX_VALUE, Integer.MAX_VALUE });
			}
		}
		int len = queries.length;
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			Integer key = tm.floorKey(queries[i]);
			if (key == null) {
				ans[i] = -1;
			} else {
				int value = tm.get(key);
				ans[i] = value == Integer.MAX_VALUE ? -1 : value;
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
